The disclosed embodiments relate generally to methods and apparatus for performing a nearest neighbor search using a hardware accelerator.
Nearest neighbor search (NNS) is an optimization problem for finding the closest (or most similar) data points to a query point, where each data and query point represents an object such as a photograph. Closeness is typically expressed in terms of a dissimilarity function: the less similar the objects, the larger the function values. Data points are often represented as d-dimensional vectors, where dissimilarity is measured using a distance metric such as the Euclidean distance.
There are numerous variants of the NNS problem. The two most well-known variants are the k-nearest neighbor search (kNN) and the approximate nearest neighbor search. A kNN search identifies the top k nearest neighbors to the query. An approximate nearest neighbor search is not guaranteed to provide the actual nearest neighbors in every case, in return for improved speed or memory savings.
The nearest neighbor search problem arises in numerous fields of application. Typically, modern products and technologies implement kNN search on traditional central processing units (CPUs).